package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.Arrays;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母（大写和/或小写）组成
 */
public class LongestPalindrome {

    /**
     * 动态规划
     * dp[i][j] = {
     * true, i == j
     * false, i != j && s[i] != s[j]
     * true, i != j && s[i] == s[j] && j - i < 3
     * dp[i + 1][j - 1], i != j && s[i] == s[j] && j - i >= 3
     * }
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; ++i) {
            dp[i][i] = true;
        }
        int begin = 0, maxLen = 1;
        for (int subLen = 2; subLen <= len; ++subLen) {
            for (int i = 0; i < len; i++) {
                int j = i + subLen - 1;
                if (j >= len){
                    break;
                }
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (subLen < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && maxLen < subLen) {
                    maxLen = subLen;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }


    /**
     * 暴力破解
     */
    public String longestPalindrome1(String s) {
        int size = s.length();
        int max = -1;
        String maxStr = "";
        for (int i = 0; i < size; ++i){
            for (int j = size - 1; j >= i; --j){
                int len = j - i;
                if (len <= max) break;
                if(check(s, i, j)){
                    max = len;
                    maxStr = s.substring(i, j+1);
                }
            }
            if (size - i <= max) break;
        }
        return maxStr;
    }

    private boolean check(String s, int i, int j){
        while (i < j){
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }

    /**
     * 中心扩散
     */
    public String longestPalindrome2(String s) {
        int len = s.length();
        int begin = 0, end = 0;
        for (int i = 0; i < len; ++i){
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int l = Math.max(len1, len2);
            if (l > end - begin){
                begin = i - (l - 1) / 2;
                end = i + l / 2;
            }
        }
        return s.substring(begin, end + 1);
    }

    public int expand(String s, int i, int j){
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            i--;
            j++;
        }
        return j - i - 1;
    }

    public static void main(String[] args) {
        String s = "cccc";
        // 动态规划
        System.out.println(new LongestPalindrome().longestPalindrome(s));
        // 暴力破解
        System.out.println(new LongestPalindrome().longestPalindrome1(s));
        // 中心扩散
        System.out.println(new LongestPalindrome().longestPalindrome2(s));
    }

}
